//
// Created by Lenovo on 2024/3/2.
//
#include<bits/stdc++.h>
using namespace std;
//k次取反后最大的数组和
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        //尽可能的将负数取反
        for(int i=0;i<nums.size();i++){
            if(k>0 && nums[i]<0){
                nums[i]=-nums[i];
                k--;
            }
        }
        //要么k还有剩余，负数已经没了；要么还有负数，k没了（后者无需处理，前者只需处理单词剩余）
        if(k>0 && k%2!=0){
            int min=nums[0],minIndex=0;
            for(int i=1;i<nums.size();i++){
                if(nums[i]<min) {
                    min=nums[i];
                    minIndex=i;
                }
            }
            nums[minIndex]=-nums[minIndex];
        }
        int sum=0;
        for(int i=0;i<nums.size();i++) sum+=nums[i];
        return sum;
    }
};
